<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(C卷,100分)- 寻找相同子串（Java & JS & Python & C）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h3 id="main-toc">题目描述</h3> 
<p>给你两个字符串t和p&#xff0c;要求从t中找到一个和p相同的连续子串&#xff0c;并输出该子串第一个字符的下标。</p> 
<h3 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0"><br /> 输入描述</h3> 
<ul><li>输入文件包括两行 分别表示字符串t和p</li><li>保证t的长度不小于p</li><li>且t的长度不超过1000000</li><li>p的长度不超过10000</li></ul> 
<h3 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0"><br /> 输出描述</h3> 
<ul><li>如果能从t中找到一个和p相等的连续子串&#xff0c;则输出该子串第一个字符在t中的下标&#xff0c;下标从左到右依次为1,2,3,…&#xff1b;</li><li>如果不能&#xff0c;则输出 “No”</li><li>如果含有多个这样的子串&#xff0c;则输出第一个字符下标最小的<br />  </li></ul> 
<h3 id="%E7%94%A8%E4%BE%8B">用例</h3> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:69px;">输入</td><td style="width:429px;">AVERDXIVYERDIAN<br /> RDXI</td></tr><tr><td style="width:69px;">输出</td><td style="width:429px;">4</td></tr><tr><td style="width:69px;">说明</td><td style="width:429px;">无</td></tr></tbody></table> 
<p></p> 
<h3>语言内置库函数实现</h3> 
<p>这题目的应该是想考察子串查找算法&#xff0c;可以考虑使用KMP算法。</p> 
<p>但是高级语言大多已经内置实现了这些算法&#xff0c;比如Java的String的indexOf&#xff0c;JS的String.prototype.indexOf&#xff0c;Python的find函数</p> 
<p></p> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);
    System.out.println(getResult(sc.nextLine(), sc.nextLine()));
  }

  public static String getResult(String str, String subStr) {
    if (str.length() &lt; subStr.length()) {
      return &#34;No&#34;;
    }

    int idx &#61; str.indexOf(subStr);
    if (idx &#61;&#61; -1) return &#34;No&#34;;
    else return idx &#43; 1 &#43; &#34;&#34;;
  }
}
</code></pre> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E4%BB%A3%E7%A0%81">JS算法代码</h4> 
<pre><code class="language-javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline &#61; require(&#34;readline&#34;);

const rl &#61; readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines &#61; [];
rl.on(&#34;line&#34;, (line) &#61;&gt; {
  lines.push(line);
  if (lines.length &#61;&#61;&#61; 2) {
    getSubIndex(...lines);
    lines.length &#61; 0;
  }
});

/* 寻找相同子串 */
function getSubIndex(str, substr) {
  if (str.length &lt; substr.length) {
    return console.log(&#34;No&#34;);
  }

  const index &#61; str.indexOf(substr);
  if (index &#61;&#61;&#61; -1) {
    return console.log(&#34;No&#34;);
  } else {
    return console.log(index &#43; 1);
  }
}
</code></pre> 
<p></p> 
<h4>Python算法源码</h4> 
<pre><code class="language-python"># 输入获取
str &#61; input()
subStr &#61; input()


# 算法入口
def getResult():
    if len(str) &lt; len(subStr):
        return &#34;No&#34;

    idx &#61; str.find(subStr)
    if idx &#61;&#61; -1:
        return &#34;No&#34;
    else:
        return idx &#43; 1


# 算法调用
print(getResult())
</code></pre> 
<p></p> 
<h4>C算法源码</h4> 
<pre><code class="language-cpp">#include &lt;stdio.h&gt;
#include &lt;string.h&gt;
#include &lt;stdlib.h&gt;

#define MAX_T_LEN 1000000
#define MAX_P_LEN 10000

int main() {
    char t[MAX_T_LEN];
    gets(t);

    char p[MAX_P_LEN];
    gets(p);

    char* point &#61; strstr(t, p);

    if(point &#61;&#61; NULL) {
        puts(&#34;No&#34;);
    } else {
        printf(&#34;%lld\n&#34;, point - t &#43; 1);
    }

    return 0;
}
</code></pre> 
<p></p> 
<h3>KMP算法实现</h3> 
<p>KMP算法原理请看&#xff1a;<a href="https://blog.csdn.net/qfc_128220/article/details/131311563?spm&#61;1001.2014.3001.5501" title="算法设计 - KMP算法_伏城之外的博客-CSDN博客">算法设计 - KMP算法_伏城之外的博客-CSDN博客</a></p> 
<p></p> 
<h4>JS算法源码</h4> 
<pre><code class="language-javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline &#61; require(&#34;readline&#34;);

const rl &#61; readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines &#61; [];
rl.on(&#34;line&#34;, (line) &#61;&gt; {
  lines.push(line);
  if (lines.length &#61;&#61;&#61; 2) {
    const t &#61; lines[0];
    const p &#61; lines[1];

    const idx &#61; indexOf(t, p);

    if (idx &#61;&#61; -1) {
      console.log(&#34;No&#34;);
    } else {
      console.log(idx &#43; 1);
    }

    lines.length &#61; 0;
  }
});

/**
 * &#64;param {*} s 正文串
 * &#64;param {*} t 模式串
 * &#64;returns 在s中查找与t相匹配的子串&#xff0c;如果成功找到&#xff0c;则返回匹配的子串第一个字符在主串中的位置
 */
function indexOf(s, t) {
  let next &#61; getNext(t);

  let i &#61; 0; // 扫描S串的指针
  let j &#61; 0; // 扫描T串的指针

  // 如果 i 指针扫描到S串结束位置&#xff0c;或者 j 指针扫描到T串的结束位置&#xff0c;都应该结束查找
  while (i &lt; s.length &amp;&amp; j &lt; t.length) {
    if (s[i] &#61;&#61; t[j]) {
      // 如果 s[i] &#61;&#61; t[j]&#xff0c;则当前位置匹配成功&#xff0c;继续匹配下一个位置
      i&#43;&#43;;
      j&#43;&#43;;
    } else {
      // 如果 s[i] !&#61; t[j]&#xff0c;则说明当前位置匹配失败&#xff0c;
      // 根据KMP算法&#xff0c;我们只需要回退T串的 j 指针到 next[j-1]位置,即最长相同前缀的结束位置后面一个位置&#xff0c;而S串的 i 指针保持不动
      if (j &gt; 0) {
        j &#61; next[j - 1];
      } else {
        // 如果 j &#61; 0,则说明S子串subS和T在第一个字符上就匹配不上, 此时T不匹配字符T[j]前面已经没有前后缀了&#xff0c;因此只能匹配下一个S子串
        i&#43;&#43;;
      }
    }
  }

  // 如果最终可以在S串中找到匹配T的子串&#xff0c;则T串的所有字符都应该被j扫描过&#xff0c;即最终 j &#61; t.length
  if (j &gt;&#61; t.length) {
    // 则S串中匹配T的子串的首字符位置应该在 i - t.length位置&#xff0c;因为 i 指针最终会扫描到S串中匹配T的子串的结束位置的后一个位置
    return i - j;
  } else {
    // 否则就是没有在S中找到匹配T的子串
    return -1;
  }
}

function getNext(t) {
  const next &#61; new Array(t.length).fill(0);

  let i &#61; 1;
  let j &#61; 0;

  while (i &lt; t.length) {
    if (t[i] &#61;&#61; t[j]) {
      next[i] &#61; j &#43; 1;
      i&#43;&#43;;
      j&#43;&#43;;
    } else {
      if (j &gt; 0) {
        j &#61; next[j - 1];
      } else {
        i&#43;&#43;;
      }
    }
  }

  return next;
}
</code></pre> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);
    String t &#61; sc.nextLine();
    String p &#61; sc.nextLine();

    int idx &#61; indexOf(t, p);

    if (idx &#61;&#61; -1) {
      System.out.println(&#34;No&#34;);
    } else {
      System.out.println(idx &#43; 1);
    }
  }

  /**
   * &#64;param s 正文串
   * &#64;param t 模式串
   * &#64;return 在s中查找与t相匹配的子串&#xff0c;如果成功找到&#xff0c;则返回匹配的子串第一个字符在主串中的位置
   */
  public static int indexOf(String s, String t) {
    int[] next &#61; getNext(t);

    int i &#61; 0; // 扫描S串的指针
    int j &#61; 0; // 扫描T串的指针

    // 如果 i 指针扫描到S串结束位置&#xff0c;或者 j 指针扫描到T串的结束位置&#xff0c;都应该结束查找
    while (i &lt; s.length() &amp;&amp; j &lt; t.length()) {
      // 如果 s[i] &#61;&#61; t[j]&#xff0c;则当前位置匹配成功&#xff0c;继续匹配下一个位置
      if (s.charAt(i) &#61;&#61; t.charAt(j)) {
        i&#43;&#43;;
        j&#43;&#43;;
      } else {
        // 如果 s[i] !&#61; t[j]&#xff0c;则说明当前位置匹配失败&#xff0c;
        // 根据KMP算法&#xff0c;我们只需要回退T串的 j 指针到 next[j-1]位置,即最长相同前缀的结束位置后面一个位置&#xff0c;而S串的 i 指针保持不动
        if (j &gt; 0) {
          j &#61; next[j - 1];
        } else {
          // 如果 j &#61; 0,则说明S子串subS和T在第一个字符上就匹配不上, 此时T不匹配字符T[j]前面已经没有前后缀了&#xff0c;因此只能匹配下一个S子串
          i&#43;&#43;;
        }
      }
    }

    // 如果最终可以在S串中找到匹配T的子串&#xff0c;则T串的所有字符都应该被j扫描过&#xff0c;即最终 j &#61; t.length
    if (j &#61;&#61; t.length()) {
      // 则S串中匹配T的子串的首字符位置应该在 i - t.length位置&#xff0c;因为 i 指针最终会扫描到S串中匹配T的子串的结束位置的后一个位置
      return i - j;
    } else {
      // 否则就是没有在S中找到匹配T的子串
      return -1;
    }
  }

  public static int[] getNext(String t) {
    int[] next &#61; new int[t.length()];

    // 由于是将T串看出两部分&#xff0c;分别是后缀部分SS&#xff0c;和前缀部分TT
    int j &#61; 1; // j 用于扫描SS&#xff0c;由于含有前、后缀的串长度至少为2&#xff0c;因此 j 扫描后缀部分的话&#xff0c;至少从1开始
    int k &#61; 0; // k 用于扫描TT

    // j 扫描结束
    while (j &lt; t.length()) {
      if (t.charAt(j) &#61;&#61; t.charAt(k)) {
        next[j] &#61; k &#43; 1;
        j&#43;&#43;;
        k&#43;&#43;;
      } else {
        if (k &gt; 0) {
          k &#61; next[k - 1];
        } else {
          j&#43;&#43;;
        }
      }
    }

    return next;
  }
}
</code></pre> 
<h4>Python算法源码</h4> 
<pre><code class="language-python"># 输入获取
t &#61; input()
p &#61; input()


# 生成前缀表
def getNext(t):
    next &#61; [0] * len(t)

    j &#61; 1
    k &#61; 0

    while j &lt; len(t):
        if t[j] &#61;&#61; t[k]:
            next[j] &#61; k &#43; 1
            j &#43;&#61; 1
            k &#43;&#61; 1
        else:
            if k &gt; 0:
                k &#61; next[k - 1]
            else:
                j &#43;&#61; 1

    return next


# KMP算法
def indexOf(s, t):
    &#34;&#34;&#34;
    :param s: 正文串
    :param t: 模式串
    :return: 在s中查找与t相匹配的子串&#xff0c;如果成功找到&#xff0c;则返回匹配的子串第一个字符在主串中的位置
    &#34;&#34;&#34;

    next &#61; getNext(t)

    # 手算的T串&#34;cabaa&#34;对应的前缀表
    # next &#61; [0, 0, 0, 0, 0]

    i &#61; 0  # 扫描S串的指针
    j &#61; 0  # 扫描T串的指针

    # 如果 i 指针扫描到S串结束位置&#xff0c;或者 j 指针扫描到T串的结束位置&#xff0c;都应该结束查找
    while i &lt; len(s) and j &lt; len(t):
        # 如果 s[i] &#61;&#61; t[j]&#xff0c;则当前位置匹配成功&#xff0c;继续匹配下一个位置
        if s[i] &#61;&#61; t[j]:
            i &#43;&#61; 1
            j &#43;&#61; 1
        else:
            # 如果 s[i] !&#61; t[j]&#xff0c;则说明当前位置匹配失败
            # 根据KMP算法&#xff0c;我们只需要回退T串的 j 指针到 next[j-1]位置,即最长相同前缀的结束位置后面一个位置&#xff0c;而S串的 i 指针保持不动
            if j &gt; 0:
                j &#61; next[j - 1]
            else:
                # 如果 j &#61; 0,则说明S子串subS和T在第一个字符上就匹配不上, 此时T不匹配字符T[j]前面已经没有前后缀了&#xff0c;因此只能匹配下一个S子串
                i &#43;&#61; 1

    # 如果最终可以在S串中找到匹配T的子串&#xff0c;则T串的所有字符都应该被j扫描过&#xff0c;即最终 j &#61; t.length
    if j &gt;&#61; len(t):
        # 则S串中匹配T的子串的首字符位置应该在 i - t.length位置&#xff0c;因为 i 指针最终会扫描到S串中匹配T的子串的结束位置的后一个位置
        return i - j
    else:
        # 否则就是没有在S中找到匹配T的子串
        return -1


# 算法入口
def getResult():
    idx &#61; indexOf(t, p)

    if idx &#61;&#61; -1:
        print(&#34;No&#34;)
    else:
        print(idx &#43; 1)


# 算法调用
getResult()
</code></pre> 
<p></p> 
<h4>C算法源码</h4> 
<pre><code class="language-cpp">#include &lt;stdio.h&gt;
#include &lt;string.h&gt;
#include &lt;stdlib.h&gt;

#define MAX_T_LEN 1000000
#define MAX_P_LEN 10000

int *getNext(char *t);
int indexOf(char *s, char *t);

int main() {
    char t[MAX_T_LEN];
    gets(t);

    char p[MAX_P_LEN];
    gets(p);

    int idx &#61; indexOf(t, p);

    if (idx &#61;&#61; -1) {
        puts(&#34;No&#34;);
    } else {
        printf(&#34;%d\n&#34;, idx &#43; 1);
    }

    return 0;
}

/*!
 *
 * &#64;param s 正文串
 * &#64;param t 模式串
 * &#64;return 在s中查找与t相匹配的子串&#xff0c;如果成功找到&#xff0c;则返回匹配的子串第一个字符在主串中的位置
 */
int indexOf(char *s, char *t) {
    int *next &#61; getNext(t);

    int sLen &#61; strlen(s);
    int tLen &#61; strlen(t);

    // 扫描S串的指针
    int i &#61; 0;
    // 扫描T串的指针
    int j &#61; 0;

    // 如果 i 指针扫描到S串结束位置&#xff0c;或者 j 指针扫描到T串的结束位置&#xff0c;都应该结束查找
    while (i &lt; sLen &amp;&amp; j &lt; tLen) {
        // 如果 s[i] &#61;&#61; t[j]&#xff0c;则当前位置匹配成功&#xff0c;继续匹配下一个位置
        if (s[i] &#61;&#61; t[j]) {
            i&#43;&#43;;
            j&#43;&#43;;
        } else {
            // 如果 s[i] !&#61; t[j]&#xff0c;则说明当前位置匹配失败&#xff0c;
            // 根据KMP算法&#xff0c;我们只需要回退T串的 j 指针到 next[j-1]位置,即最长相同前缀的结束位置后面一个位置&#xff0c;而S串的 i 指针保持不动
            if (j &gt; 0) {
                j &#61; next[j - 1];
            } else {
                // 如果 j &#61; 0,则说明S子串subS和T在第一个字符上就匹配不上, 此时T不匹配字符T[j]前面已经没有前后缀了&#xff0c;因此只能匹配下一个S子串
                i&#43;&#43;;
            }
        }
    }

    // 如果最终可以在S串中找到匹配T的子串&#xff0c;则T串的所有字符都应该被j扫描过&#xff0c;即最终 j &#61; t.length
    if (j &#61;&#61; tLen) {
        // 则S串中匹配T的子串的首字符位置应该在 i - t.length位置&#xff0c;因为 i 指针最终会扫描到S串中匹配T的子串的结束位置的后一个位置
        return i - j;
    } else {
        // 否则就是没有在S中找到匹配T的子串
        return -1;
    }
}

int *getNext(char *t) {
    int tLen &#61; strlen(t);

    int *next &#61; (int *) malloc(sizeof(int) * tLen);
    for (int i &#61; 0; i &lt; tLen; i&#43;&#43;) {
        next[i] &#61; 0;
    }

    // 由于是将T串看出两部分&#xff0c;分别是后缀部分SS&#xff0c;和前缀部分TT
    int j &#61; 1; // j 用于扫描SS&#xff0c;由于含有前、后缀的串长度至少为2&#xff0c;因此 j 扫描后缀部分的话&#xff0c;至少从1开始
    int k &#61; 0; // k 用于扫描TT

    // j 扫描结束
    while (j &lt; tLen) {
        if (t[j] &#61;&#61; t[k]) {
            next[j] &#61; k &#43; 1;
            j&#43;&#43;;
            k&#43;&#43;;
        } else {
            if (k &gt; 0) {
                k &#61; next[k - 1];
            } else {
                j&#43;&#43;;
            }
        }
    }

    return next;
}</code></pre> 
<p></p>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>